Diffusing update algorithm
part 4/5 · 7.7 KB total
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
If all the successor routes to a destination fail, the feasible successor becomes the successor and is immediately added to the routing table. If there is no feasible successor in the topology table, a query process is initiated to look for a new route.
Example
Legend:
+ = Router
− or | = Link
(X) = Metric of link
A (2) B (1) C
+ - - - - - + - - - - - +
| |
(2)| | (3)
| |
+ - - - - - +
D (1) E
Now a client on router E wants to talk to a client on router A. That means a route between router A and router E must be available. This route is calculated as follows:
The immediate neighbours of router E are router C and router D. DUAL in router E asks for the reported distance (RD) from routers C and D respectively to router A. The following are the results:
Destination: Router A
via D: RD(4)
via C: RD(3)
The route via C is therefore in the lowest cost. In the next step, the distance from router E to the neighbours are added to the reported distance to get the feasible distance (FD):
Destination: Router A
via D: RD(4), FD(5)
via C: RD(3), FD(6)
DUAL therefore finds that the route via D has the least total cost. Then the route via D will be marked as "successor", equipped with passive status and registered in the routing table. The route via C is kept as a "feasible successor", because its RD is less than the FD of the successor:
Destination: Router A
via D: RD(4), FD(5) successor
via C: RD(3), FD(6) feasible successor
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────